#include<stdio.h>
#include<stdlib.h>
#include<unistd.h>
#include<string.h>
#include<sys/types.h>
#include<sys/stat.h>
#include<fcntl.h>
#include<sys/time.h>


void MergeSort(int *A, int n);
void Merge(int *A, int m, int n);

int *B;

int main(int argc, char **argv)
{
	struct timeval start, end, time;

	int N, i;
	int fd, op_fd;
	char s[100];
	int *A;

	if(argc < 3)
	{
		printf("./a.out <filename> <N>\n");
		return 0;
	}

	gettimeofday(&start, NULL);

	strcpy(s, argv[1]);
	N = atoi(argv[2]);

	if((fd = open(s, O_RDONLY)) == -1)
	{
		perror("Cannot opne file\n");
	}

	A = (int *) malloc(sizeof(int) * N);
	B = (int *) malloc(sizeof(int) * N);

	if((A == NULL) || (B == NULL))
	{
		perror("malloc error\n");
	}

	if(read(fd, A, N*sizeof(int)) == -1)
	{
		perror("Cannot read file\n");
	}

	MergeSort(A, N);
/*
	for(i=0; i<N; i++)
	{
		printf("%d ", B[i]);
	}
*/	
	if((op_fd = open("data/result", O_CREAT|O_RDWR, 0700)) == -1)
	{
		perror("o/p file open failed\n");
	}

	if(write(op_fd, A, N*sizeof(int)) == -1)
	{
		perror("Write failed\n");
	}

	gettimeofday(&end, NULL);
	timersub(&end, &start, &time);

	printf("Merge Sort : N = %d | time = %lf\n", N, time.tv_sec + time.tv_usec/1000000.0);

	free(A);
	free(B);

	return 0;
}

void MergeSort(int *A, int n)
{
	int m;
	
	if(n>1)
	{
		m = n/2;
		MergeSort(A, m);
		MergeSort(A+m, n-m);
		Merge(A, m, n);
	}
}

void Merge(int *A, int m, int n)
{
	int i = 0, j = m, k;

	for(k = 0; k < n; k++)
	{
		if(j > (n-1))
		{
			B[k] = A[i];
			i = i+1;
		}
		else if(i > (m-1))
		{
			B[k] = A[j];
			j = j+1;
		}
		else if(A[i] < A[j])
		{
			B[k] = A[i];
			i = i+1;
		}
		else
		{
			B[k] = A[j];
			j = j+1;
		}
	}

	for(k=0; k < n; k++)
	{
		A[k] = B[k];
	}
}
